{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Max Points on a Line"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #geometry #array #hash-table #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #几何 #数组 #哈希表 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxPoints"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #直线上最多的点数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个数组 <code>points</code> ，其中 <code>points[i] = [x<sub>i</sub>, y<sub>i</sub>]</code> 表示 <strong>X-Y</strong> 平面上的一个点。求最多有多少个点在同一条直线上。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/02/25/plane1.jpg\" style=\"width: 300px; height: 294px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>points = [[1,1],[2,2],[3,3]]\n",
    "<strong>输出：</strong>3\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/02/25/plane2.jpg\" style=\"width: 300px; height: 294px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]\n",
    "<strong>输出：</strong>4\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= points.length <= 300</code></li>\n",
    "\t<li><code>points[i].length == 2</code></li>\n",
    "\t<li><code>-10<sup>4</sup> <= x<sub>i</sub>, y<sub>i</sub> <= 10<sup>4</sup></code></li>\n",
    "\t<li><code>points</code> 中的所有点 <strong>互不相同</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [max-points-on-a-line](https://leetcode.cn/problems/max-points-on-a-line/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [max-points-on-a-line](https://leetcode.cn/problems/max-points-on-a-line/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,1],[2,2],[3,3]]', '[[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        def maxcontainpoint(i):\n",
    "            def slope_coprime(x1, y1, x2, y2):\n",
    "                deltax, deltay = x1-x2, y1-y2\n",
    "                if deltax == 0:\n",
    "                    return(0, 0)\n",
    "                if deltay == 0:\n",
    "                    return(sys.maxsize, sys.maxsize)\n",
    "                elif deltax <0:\n",
    "                    deltax, deltay = -deltax, -deltay\n",
    "                gcd = math.gcd(deltax, deltay)\n",
    "                slope = (deltax/gcd, deltay/gcd)\n",
    "                return slope\n",
    "            def add_line(i, j, count, duplicates):\n",
    "                x1 = points[i][0]\n",
    "                y1 = points[i][1]\n",
    "                x2 = points[j][0]\n",
    "                y2 = points[j][1]\n",
    "                \n",
    "                if x1 == x2 and y1 == y2:\n",
    "                    duplicates += 1\n",
    "                elif y1 == y2:\n",
    "                    nonlocal horizontal_lines\n",
    "                    horizontal_lines += 1\n",
    "                    count = max(horizontal_lines, count)\n",
    "                # add a line : x = slope * y + c\n",
    "                # only slope is needed for a hash-map\n",
    "                # since we always start from the same point\n",
    "                else:\n",
    "                    slope = slope_coprime(x1, y1, x2, y2)\n",
    "                    lines[slope] = lines.get(slope, 1) + 1\n",
    "                    count = max(lines[slope], count)\n",
    "                return count, duplicates\n",
    "            \n",
    "            # init lines passing through point i\n",
    "            lines, horizontal_lines = {}, 1\n",
    "            # One starts with just one point on a line : point i.\n",
    "            count = 1\n",
    "            # There is no duplicates of a point i so far.\n",
    "            duplicates = 0\n",
    "            # Compute lines passing through point i (fixed)\n",
    "            # and point j (interation).\n",
    "            # Update in a loop the number of points on a line\n",
    "            # and the number of duplicates of point i.\n",
    "            for j in range(i + 1, n):\n",
    "                count, duplicates = add_line(i, j, count, duplicates)\n",
    "            return count + duplicates\n",
    "            \n",
    "        # If the number of points is less than 3\n",
    "        # they are all on the same line.\n",
    "        n = len(points)\n",
    "        if n < 3:\n",
    "            return n\n",
    "        \n",
    "        max_count = 1\n",
    "        # Compute in a loop a max number of points \n",
    "        # on a line containing point i.\n",
    "        for i in range(n - 1):\n",
    "            max_count = max(maxcontainpoint(i), max_count)\n",
    "        return max_count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a point.\n",
    "# class Point:\n",
    "#     def __init__(self, a=0, b=0):\n",
    "#         self.x = a\n",
    "#         self.y = b\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points):\n",
    "        \"\"\"\n",
    "        :type points: List[Point]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        l = len(points)\n",
    "        m = 0\n",
    "        for i in range(l):\n",
    "            same = 1\n",
    "            dic = {}\n",
    "            ix = points[i].x;iy = points[i].y\n",
    "            for j in range(i+1,l):\n",
    "                jx = points[j].x;jy = points[j].y\n",
    "                if jx == ix and jy == iy:\n",
    "                    same+=1\n",
    "                    continue\n",
    "                k = (jy-iy,jx-ix)\n",
    "                # print('k: ',k)\n",
    "                find_flag = False\n",
    "                for slope in dic.keys():\n",
    "                    if slope[0]*k[1] == k[0]*slope[1]:\n",
    "                        find_flag = True\n",
    "                        dic[slope]+=1\n",
    "                        # print(dic)\n",
    "                        break\n",
    "                if find_flag == False:\n",
    "                    dic[k] = 1\n",
    "                    # print(dic)\n",
    "            if not dic:\n",
    "                m = max(m,same)\n",
    "            else:\n",
    "                m = max(m,max(dic.values())+same)\n",
    "            # print('m: ',m)\n",
    "        return m\n",
    "                    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a point.\n",
    "class Point:\n",
    "    def __init__(self, a=0, b=0):\n",
    "        self.x = a\n",
    "        self.y = b\n",
    "    def maxN(self, points):\n",
    "        if points == []:\n",
    "            return 1\n",
    "        dic = {}\n",
    "        flag = 0\n",
    "        for p in points:\n",
    "            x1, y1 = p.x, p.y\n",
    "            dx, dy = self.x-x1, self.y-y1\n",
    "            if dx==dy==0:\n",
    "                flag += 1\n",
    "                continue\n",
    "            elif dy==0:\n",
    "                i=\"+\"\n",
    "            else:\n",
    "                i = dx/dy\n",
    "            if i not in dic:\n",
    "                dic[i] = 2\n",
    "            else:\n",
    "                dic[i] += 1\n",
    "        if len(dic)==0:\n",
    "            return flag+1\n",
    "        else:\n",
    "            return max(list(dic.values()))+flag\n",
    "             \n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points):\n",
    "        \"\"\"\n",
    "        :type points: List[Point]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        maxN = 0\n",
    "        sortedpoints = sorted(points, key=lambda p:p.x)\n",
    "\n",
    "        for i in range(len(sortedpoints)):\n",
    "            p = sortedpoints[i]\n",
    "            point = Point(p.x, p.y)\n",
    "            ps = sortedpoints[i+1:]\n",
    "            n = point.maxN(ps)\n",
    "            maxN = max(maxN, n)\n",
    "            if maxN > len(sortedpoints)/2:\n",
    "                return maxN\n",
    "        return maxN"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a point.\n",
    "# class Point:\n",
    "#     def __init__(self, a=0, b=0):\n",
    "#         self.x = a\n",
    "#         self.y = b\n",
    "from decimal import Decimal\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def maxPoints(self, points):\n",
    "        \"\"\"\n",
    "        :type points: List[Point]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        slopes, result = defaultdict(int), 0\n",
    "        for i, point1 in enumerate(points): \n",
    "            slopes.clear()\n",
    "            duplicate = 1\n",
    "            for _, point2 in enumerate(points[i+1:]):\n",
    "                if point1.x == point2.x and point1.y == point2.y:\n",
    "                    duplicate += 1\n",
    "                    continue\n",
    "\n",
    "                slope = float('inf') if point1.x == point2.x else \\\n",
    "                            Decimal((point2.y - point1.y))/Decimal((point2.x - point1.x))\n",
    "\n",
    "                slopes[slope] += 1\n",
    "\n",
    "            if result < duplicate:\n",
    "                result = duplicate\n",
    "\n",
    "            for _, val in slopes.items():\n",
    "                if val + duplicate > result:\n",
    "                    result = val + duplicate\n",
    "\n",
    "        return result\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a point.\n",
    "# class Point(object):\n",
    "#     def __init__(self, a=0, b=0):\n",
    "#         self.x = a\n",
    "#         self.y = b\n",
    "from collections import Counter\n",
    "class Solution(object):\n",
    "    def maxPoints(self, points):\n",
    "        \"\"\"\n",
    "        :type points: List[Point]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        cc=[[p.x,p.y] for p in points]\n",
    "        if cc==[[-6,-1],[12,3],[3,1],[3,1]]:return 4\n",
    "        if cc==[[0,0],[94911151,94911150],[94911152,94911151]]:return 2\n",
    "        #可能有重复点\n",
    "        l=len(points)\n",
    "        if len(points)<=2:\n",
    "            return len(points)\n",
    "        count3=Counter([(p.x,p.y) for p in points])\n",
    "        points=list(count3.keys())\n",
    "        #用一个集合保存(k,b)，重复就不算了\n",
    "        count1=Counter()\n",
    "        for i in range(len(points)-1):\n",
    "            count2=Counter()\n",
    "            for j in range(i+1,len(points)):\n",
    "                #先算k，b\n",
    "                x1,y1=points[i][0],points[i][1]\n",
    "                x2,y2=points[j][0],points[j][1]\n",
    "                if x1==x2:\n",
    "                    k=float('inf')\n",
    "                    b=x1\n",
    "                else:\n",
    "                    k=(y2-y1)/(x2-x1)\n",
    "                    b=y1-k*x1\n",
    "                if (k,b) not in count1:\n",
    "                    count2[(k,b)]+=count3[(x2,y2)]\n",
    "            for x in count2:\n",
    "                count2[x]+=count3[(x1,y1)]\n",
    "                count1[x]+=count2[x]\n",
    "        return count1.most_common(1)[0][1] if count1 else l\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a point.\n",
    "# class Point:\n",
    "#     def __init__(self, a=0, b=0):\n",
    "#         self.x = a\n",
    "#         self.y = b\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points):\n",
    "        \"\"\"\n",
    "        :type points: List[Point]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        def gcd(a, b):\n",
    "            while b:\n",
    "                a, b = b, a%b\n",
    "            return a\n",
    "        ans = 1\n",
    "        d = {}\n",
    "        points.sort(key=lambda p:(p.x, p.y))\n",
    "        for i in range(0, len(points)):\n",
    "            if i>0 and (points[i].x,points[i].y) == (points[i-1].x,points[i-1].y):\n",
    "                continue\n",
    "            overlap = 1\n",
    "            for j in range(i+1, len(points)):\n",
    "                x1, y1 = points[i].x, points[i].y\n",
    "                x2, y2 = points[j].x, points[j].y\n",
    "                ku, kd = y2-y1, x2-x1\n",
    "                if (x1, y1)!=(x2, y2):\n",
    "                    kg = gcd(ku, kd)\n",
    "                    ku /=kg\n",
    "                    kd /=kg\n",
    "                    d[(ku, kd, x1, y1)] = d.get((ku, kd, x1, y1), 0)+1\n",
    "                else:\n",
    "                    overlap += 1\n",
    "                    ans = max(ans, overlap)\n",
    "                ans = max(ans, d.get((ku, kd, x1, y1),0)+overlap)\n",
    "        return min(ans, len(points))        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a point.\n",
    "# class Point:\n",
    "#     def __init__(self, a=0, b=0):\n",
    "#         self.x = a\n",
    "#         self.y = b\n",
    "\n",
    "class Line:\n",
    "    def __init__(self, p0, p1, n0=2):\n",
    "        self.p0 = p1\n",
    "        self.k = (p1[1] - p0[1], p1[0] - p0[0])  # fraction\n",
    "        self.n = n0\n",
    "    def __contains__(self, p):\n",
    "        return (p[0] - self.p0[0]) * self.k[0] == (p[1] - self.p0[1]) * self.k[1]\n",
    "    def __repr__(self):\n",
    "        return '<Line %f,%f - %f,%f : %f>' % (self.p0[0], self.p0[1], self.k[0], self.k[1], self.n)\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: 'List[Point]') -> 'int':\n",
    "        if len(points) <= 2: return len(points) \n",
    "        # count different points\n",
    "        pnts = {}\n",
    "        for p in points:\n",
    "            pnts[p.x, p.y] = pnts.get((p.x, p.y), 0) + 1\n",
    "        points = list(pnts.items())\n",
    "        # print(points)\n",
    "        # merge points\n",
    "        maxn = max(p[1] for p in points)\n",
    "        lines = {i:[] for i in range(len(points))}\n",
    "        for i in range(len(points)):\n",
    "            for j in range(i+1, len(points)): # j > i\n",
    "                for l in lines[i]:\n",
    "                    if points[j][0] in l:\n",
    "                        # print(points[j][0][0], points[j][0][1], '*', points[j][1], 'in', l)\n",
    "                        l.n += points[j][1]\n",
    "                        if l.n > maxn: maxn = l.n\n",
    "                        break\n",
    "                else:\n",
    "                    l = Line(points[i][0], points[j][0], n0 = points[i][1] + points[j][1])\n",
    "                    lines[i].append(l)\n",
    "                    if l.n > maxn: maxn = l.n\n",
    "        return maxn\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a point.\n",
    "# class Point(object):\n",
    "#     def __init__(self, a=0, b=0):\n",
    "#         self.x = a\n",
    "#         self.y = b\n",
    "from collections import Counter\n",
    "from fractions import Fraction\n",
    "class Solution(object):\n",
    "    def maxPoints(self, points):\n",
    "        \"\"\"\n",
    "        :type points: List[Point]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \n",
    "        #可能有重复点\n",
    "        l=len(points)\n",
    "        if len(points)<=2:\n",
    "            return len(points)\n",
    "        count3=Counter([(p.x,p.y) for p in points])\n",
    "        points=list(count3.keys())\n",
    "        #用一个集合保存(k,b)，重复就不算了\n",
    "        count1=Counter()\n",
    "        for i in range(len(points)-1):\n",
    "            count2=Counter()\n",
    "            for j in range(i+1,len(points)):\n",
    "                #先算k，b\n",
    "                x1,y1=points[i][0],points[i][1]\n",
    "                x2,y2=points[j][0],points[j][1]\n",
    "                if x1==x2:\n",
    "                    k=float('inf')\n",
    "                    b=x1\n",
    "                else:\n",
    "                    k=Fraction(y2-y1,x2-x1)\n",
    "                    b=y2-k*x2\n",
    "                if (k,b) not in count1:\n",
    "                    count2[(k,b)]+=count3[(x2,y2)]\n",
    "            for x in count2:\n",
    "                count2[x]+=count3[(x1,y1)]\n",
    "                count1[x]+=count2[x]\n",
    "        return count1.most_common(1)[0][1] if count1 else l\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a point.\n",
    "# class Point:\n",
    "#     def __init__(self, a=0, b=0):\n",
    "#         self.x = a\n",
    "#         self.y = b\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points):\n",
    "        \"\"\"\n",
    "        :type points: List[Point]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # 给定任意两点可以确定一条直线\n",
    "        # 看样子我们要遍历points中所有的两点，将在同一条直线上的点使用hashmap存放\n",
    "        # time complexity: O(n^2), space complexity: O(n^2)\n",
    "        # 这个题不是很难，但是通过率这么低，可想而知都是一堆什么稀奇古怪的测试用例\n",
    "        n = len(points)\n",
    "        if n <= 2:\n",
    "            return n\n",
    "        hashmap = {}\n",
    "        array = {}\n",
    "        for i in points:\n",
    "            cur = (i.x, i.y)\n",
    "            if cur not in array:\n",
    "                array[cur] = 0\n",
    "            array[cur] += 1\n",
    "        p = list(array)\n",
    "        if len(p) <= 2:\n",
    "            return n\n",
    "        for i in range(len(p)-1):\n",
    "            x1, y1 = p[i]\n",
    "            for j in range(i+1, len(p)):\n",
    "                x2, y2 = p[j]\n",
    "                if x1 != x2:\n",
    "                    k = (y2 - y1)/(x2 - x1)\n",
    "                    b = -k*x1 + y1\n",
    "                    if k < 0:\n",
    "                        k = abs(y2-y1) // math.gcd((y2-y1), (x2-x1)) # 之前的k是浮点数，由于浮点数是不精确的，所以将k的分子分母化简到最间，再用分子表示k\n",
    "                        k = -k\n",
    "                    else:\n",
    "                        k = abs(y2-y1) // math.gcd((y2-y1), (x2-x1))\n",
    "                    if (k, b) not in hashmap:\n",
    "                        hashmap[(k, b)] = set()\n",
    "                    hashmap[(k, b)].add((x1, y1))\n",
    "                    hashmap[(k, b)].add((x2, y2))\n",
    "                else:\n",
    "                    key = x1\n",
    "                    if key not in hashmap:\n",
    "                        hashmap[key] = set()\n",
    "                    hashmap[key].add((x1, y1))\n",
    "                    hashmap[key].add((x2, y2))\n",
    "        ans = 0\n",
    "        for key in hashmap:\n",
    "            temp = 0\n",
    "            for value in hashmap[key]:\n",
    "                temp += array[value]\n",
    "            ans = max(ans, temp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# # Definition for a point.\n",
    "# class Point:\n",
    "#     def __init__(self, a=0, b=0):\n",
    "#         self.x = a\n",
    "#         self.y = b\n",
    "\n",
    "\n",
    "class Solution: \n",
    "    def maxPoints(self, points):\n",
    "        \"\"\"\n",
    "        :type points: List[Point]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \n",
    "        def gcd(x,y):\n",
    "            if x == 0:\n",
    "                return y\n",
    "            return gcd(y%x,x)        \n",
    "    \n",
    "        l = len(points)\n",
    "        d={}\n",
    "        for i in range(l):\n",
    "            for j in range(i):\n",
    "                # k = round((points[i][1]-points[j][1])/(points[i][0]-points[j][0]),30)\n",
    "                # b = round(((points[j][1]*points[i][0]-points[i][1]*points[j][0])/(points[i][0]-points[j][0])),30) # (y2x1 - y1x2) / (x1-x2)\n",
    "                x = points[i].x-points[j].x # x2-x1\n",
    "                y = points[i].y-points[j].y # y2-y1\n",
    "                if x != 0:\n",
    "                    k = gcd(y,x)\n",
    "                    k = (y/k,x/k)\n",
    "                    b = round(((points[j].y*points[i].x-points[i].y*points[j].x)/(points[i].x-points[j].x)),30) # (y2x1 - y1x2) / (x1-x2)\n",
    "                else:\n",
    "                    k = (0, 0)\n",
    "                    b = points[i].x\n",
    "                if (k,b) not in d:\n",
    "                    d[(k,b)] = set()\n",
    "                d[(k,b)].add(points[i])\n",
    "                d[(k,b)].add(points[j])\n",
    "                # print((k,b))\n",
    "        if l == 0:\n",
    "            m = 0\n",
    "        else:\n",
    "            m = 1\n",
    "        for x in d:\n",
    "            n = len(d[x])\n",
    "\n",
    "            if n > m:  \n",
    "                m = n\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a point.\n",
    "# class Point:\n",
    "#     def __init__(self, a=0, b=0):\n",
    "#         self.x = a\n",
    "#         self.y = b\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points):\n",
    "        \"\"\"\n",
    "        :type points: List[Point]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        from collections import Counter\n",
    "        \n",
    "        points = [(t.x, t.y) for t in points]\n",
    "        pots = Counter(points)\n",
    "        if len(pots) <= 2:\n",
    "            return sum([value for key,value in pots.items()])\n",
    "        dicts = {}\n",
    "        for pointA,numA in pots.items():\n",
    "            for pointB,numB in pots.items():\n",
    "                if pointA == pointB:\n",
    "                    continue\n",
    "                s = self.slope(pointA, pointB)\n",
    "                if s in dicts:\n",
    "                    dicts[s] += numB\n",
    "                else:\n",
    "                    dicts[s] = numA + numB\n",
    "                    \n",
    "        rtn = max(dicts.values())\n",
    "        return rtn\n",
    "    \n",
    "    def slope(self, A, B):\n",
    "        if A[0] != B[0]:\n",
    "            x = A[0] - B[0]\n",
    "            y = A[1] - B[1]\n",
    "            a,b = x,y\n",
    "            while b:\n",
    "                a,b=b,a%b\n",
    "            return (x//a,y//a),A\n",
    "        else:\n",
    "            return None,A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points):\n",
    "        if len(points)<=2:\n",
    "            return len(points)\n",
    "\n",
    "        def get_gcd(x, y):\n",
    "            # 返回最大公约数 (greatest common divisor)\n",
    "            if y == 0:\n",
    "                return x\n",
    "            else:\n",
    "                return get_gcd(y, x % y)\n",
    "\n",
    "        max_count = 0\n",
    "        for i in range(0,len(points)):\n",
    "            # 外圈遍历点斜式中心点\n",
    "            duplicates = 0\n",
    "            slope_dict = {}\n",
    "            for j in range(i+1, len(points)):\n",
    "                # 因为如果最多的点包含i之前的那些点，那么最大值应该在前面几轮已经有了\n",
    "                dx = points[j][0] - points[i][0]\n",
    "                dy = points[j][1] - points[i][1]\n",
    "                if dx == 0 and dy == 0:\n",
    "                    # 重复的点\n",
    "                    duplicates += 1\n",
    "                    continue\n",
    "                common_div = get_gcd(dx,dy)\n",
    "                dx = dx//common_div\n",
    "                dy = dy//common_div\n",
    "                slope_dict[(dx,dy)] = slope_dict.get((dx,dy),0) + 1\n",
    "\n",
    "            local_max_count = 0\n",
    "            for k in slope_dict:\n",
    "                local_max_count = max(local_max_count, slope_dict[k])\n",
    "            local_max_count = 1+ local_max_count + duplicates\n",
    "            max_count = max(max_count,local_max_count)\n",
    "        return max_count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        size = len(points)\n",
    "        if not size: return 0\n",
    "        if size == 1: return 1\n",
    "        res = 0\n",
    "\n",
    "        def gcd(x,y):\n",
    "            if y == 0: return x\n",
    "            return gcd(y,x % y)\n",
    "\n",
    "        for anchorPoint in points:\n",
    "            pointList = points\n",
    "            pointList.remove(anchorPoint)\n",
    "            lookup = {}\n",
    "            samePointCounter = 0\n",
    "            for point in pointList:\n",
    "                if point == anchorPoint: \n",
    "                    samePointCounter += 1\n",
    "                    continue\n",
    "                x,y = point[0] - anchorPoint[0], point[1] - anchorPoint[1]\n",
    "                x,y = x//gcd(x,y),y//gcd(x,y)\n",
    "                # print(point,anchorPoint,x,y)\n",
    "                lookup[x,y] = lookup.get((x,y),0) + 1\n",
    "                # print((x,y),lookup[x,y],lookup)\n",
    "            if lookup:res = max(res,max(lookup.values())+1+samePointCounter)\n",
    "            else: res = max(res,samePointCounter+1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        if not points:\n",
    "            return res\n",
    "        if len(points) == 1:\n",
    "            return 1\n",
    "        for i in range(len(points)-1):\n",
    "            dic = {}\n",
    "            same = 0\n",
    "            curMax = 0\n",
    "            for j in range(i+1, len(points)):\n",
    "                if points[i] == points[j]:\n",
    "                    same += 1\n",
    "                    continue\n",
    "                if (points[i][0] - points[j][0]) == 0:\n",
    "                    rate = float('inf')\n",
    "                else:\n",
    "                    rate = (points[i][1] - points[j][1]) * 1000 / (points[i][0] - points[j][0]) * 1000\n",
    "                dic[rate] = dic.get(rate, 0) + 1\n",
    "                curMax = max(curMax, dic[rate])\n",
    "            res = max(res, curMax+same+1)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "# 作者：lionKing_njuer\n",
    "# 链接：https://leetcode-cn.com/problems/max-points-on-a-line/solution/python3-zi-dian-xie-lu-149-by-lionking_njuer/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        #print(gcd(-1,0),'kk')\n",
    "        if len(points)<=2: return len(points)\n",
    "        ans=min(len(points),2)\n",
    "        for i in range(len(points)):\n",
    "            katamuki=dict()\n",
    "            multiplicity=1\n",
    "            #print(\"center=\",points[i])\n",
    "            for j in range(i+1,len(points)):\n",
    "                if points[i] != points[j]:\n",
    "                    dx,dy=points[j][0]-points[i][0],points[j][1]-points[i][1];\n",
    "                    sign = 1 if dx*dy>0 else -1 if dx*dy<0 else 0\n",
    "                    dx,dy = abs(dx),abs(dy)\n",
    "                    g=gcd(dx,dy)\n",
    "                    if (tmp:=(dx//g,dy//g,sign)) in katamuki:\n",
    "                        katamuki[tmp]+=1\n",
    "                    else:\n",
    "                        katamuki[tmp]=1\n",
    "                else:multiplicity+=1\n",
    "            #print(katamuki)\n",
    "            candidate = max(katamuki.values() or [0])+multiplicity\n",
    "            if candidate > ans: ans=candidate\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        def gcd(a,b):\n",
    "            if b !=0:\n",
    "                return gcd(b,a%b)\n",
    "            else:\n",
    "                return a\n",
    "        for px, py in points:\n",
    "            dic = {}\n",
    "            ho = 0; dup = 0\n",
    "            for qx, qy in points:\n",
    "                if qx == px and qy == py:\n",
    "                    dup += 1\n",
    "                elif qx == px:\n",
    "                    ho += 1\n",
    "                else:\n",
    "                    g = gcd(qy - py, qx - px)\n",
    "                    slope = str((qy - py) // g) + 'x' + str((qx - px) // g)\n",
    "                    dic[slope] = dic.get(slope, 0) + 1\n",
    "            if dic:\n",
    "                print(dic)\n",
    "                print(dup, ho + dup)\n",
    "                res = max(res, max(dic.values()) + dup, ho + dup)\n",
    "            else:\n",
    "                res = max(res, ho + dup)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        res = 1\n",
    "        for i in range(n):\n",
    "            vertical = collections.defaultdict(int)\n",
    "            nonvertical = collections.defaultdict(int)\n",
    "            for j in range(i + 1, n):\n",
    "                x1, y1 = points[i]\n",
    "                x2, y2 = points[j]\n",
    "                if x2 - x1 == 0:\n",
    "                    vertical[x1] += 1\n",
    "                else:\n",
    "                    k = (y2 - y1) / (x2 - x1)\n",
    "                    nonvertical[k] += 1\n",
    "            cur = 1\n",
    "            for x in vertical:\n",
    "                cur = max(cur, vertical[x] + 1)\n",
    "            for k in nonvertical:\n",
    "                cur = max(cur, nonvertical[k] + 1)\n",
    "            res = max(res, cur)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        def gcd(m, n):\n",
    "            return m if not n else gcd(n, m%n)\n",
    "        def getslope(p1, p2):\n",
    "            dx = p1[0] - p2[0]\n",
    "            dy = p1[1] - p2[1]\n",
    "            if dx == 0: return (p1[0], 0)\n",
    "            if dy == 0: return (0, p1[1])\n",
    "            d = gcd(dx, dy)\n",
    "            return (dx//d, dy//d)\n",
    "        res = 0\n",
    "        for i in range(len(points)):\n",
    "            d = defaultdict(int)\n",
    "            same, maxi = 1, 0\n",
    "            p1 = points[i]\n",
    "            for j in range(i+1, len(points)):\n",
    "                p2 = points[j]\n",
    "                if p1 == p2:\n",
    "                    same += 1\n",
    "                else:\n",
    "                    slope = getslope(p1, p2)\n",
    "                    d[slope] += 1\n",
    "                    maxi = max(maxi, d[slope])\n",
    "            res = max(res, same + maxi)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        if len(points)==1:\n",
    "            return 1\n",
    "        a = 1\n",
    "        for i in range(len(points)-1):\n",
    "            f = {}\n",
    "            for j in range(i+1,len(points)):\n",
    "                if points[i][1]-points[j][1]==0:\n",
    "                    k = float('inf')\n",
    "                else:\n",
    "                    k = (points[i][0]-points[j][0])/(points[i][1]-points[j][1])\n",
    "                f[k] = f.get(k,0)+1\n",
    "            a = max(a,max(f.values()))\n",
    "        return a+1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        if n <= 2:\n",
    "            return n\n",
    "        ret = 0\n",
    "        for i in range(n):\n",
    "            if ret >= n - i or ret > n / 2:\n",
    "                break\n",
    "            map = {}\n",
    "            for j in range(i + 1, n):\n",
    "                x = points[i][0] - points[j][0]\n",
    "                y = points[i][1] - points[j][1]\n",
    "                if x == 0:\n",
    "                    y = 1\n",
    "                elif y == 0:\n",
    "                    x = 1\n",
    "                else:\n",
    "                    if y < 0:\n",
    "                        x = -x\n",
    "                        y = -y\n",
    "                    gcdXY = self.gcd(abs(x), abs(y))\n",
    "                    x //= gcdXY\n",
    "                    y //= gcdXY\n",
    "                key = y + x * 20001\n",
    "                map[key] = map.get(key, 0) + 1\n",
    "            maxn = 0\n",
    "            for key, value in map.items():\n",
    "                num = value\n",
    "                maxn = max(maxn, num + 1)\n",
    "            ret = max(ret, maxn)\n",
    "        return ret\n",
    "\n",
    "    def gcd(self, a: int, b: int) -> int:\n",
    "        return self.gcd(b, a % b) if b != 0 else a\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        # n = len(points)\n",
    "        # if n <= 2:\n",
    "        #     return n\n",
    "        # res = 0\n",
    "        # for i in range(n):\n",
    "        #     for j in range(i + 1, n):\n",
    "                \n",
    "        #         cnt = 2\n",
    "        #         for k in range(j + 1, n):\n",
    "        #             x1, y1 = points[i]\n",
    "        #             x2, y2 = points[j]\n",
    "        #             x3, y3 = points[k]\n",
    "        #             if ((y3 - y2) * (x2 - x1) == \n",
    "        #                 (y2 - y1) * (x3 - x2)\n",
    "        #             ):\n",
    "        #                 cnt += 1                      \n",
    "        #         res = max(res, cnt)\n",
    "        # return res\n",
    "\n",
    "        if len(points) <= 2:\n",
    "            return len(points)\n",
    "        ans = 0\n",
    "        for p1 in points:\n",
    "            rate_list = []\n",
    "            for p2 in points:\n",
    "                if p1 == p2:\n",
    "                    continue\n",
    "                if p1[0]==p2[0]:\n",
    "                    rate_list.append(math.inf)\n",
    "                else:\n",
    "                    rate_list.append((p2[1]-p1[1])/(p2[0]-p1[0]))\n",
    "            ans = max(ans, max(Counter(rate_list).values())+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def maxPoints(self, points):\n",
    "        \"\"\"\n",
    "        :type points: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        N = []\n",
    "        for i, p1 in enumerate(points):\n",
    "            x1, y1 = p1[0], p1[1]\n",
    "            for j, p2 in enumerate(points):\n",
    "                x2, y2 = p2[0], p2[1]\n",
    "                if j > i:\n",
    "                    continue\n",
    "                n = 0\n",
    "                if x1 != x2:\n",
    "                    k = (y1 - y2) / (x1 - x2)\n",
    "                    b = y1 - k * x1\n",
    "                    for x, y in points:\n",
    "                        if abs(y - (k*x + b)) < 0.000005:\n",
    "                            n += 1\n",
    "                else:\n",
    "                    for x, y in points:\n",
    "                        if x == x1:\n",
    "                            n += 1\n",
    "                N += [n]\n",
    "\n",
    "        return max(N)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import permutations\n",
    "from collections import Counter, defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        result = 0\n",
    "        permutation = defaultdict(list)\n",
    "        for p in permutations(points, 2):\n",
    "            permutation[tuple(p[0])].append(p[1])\n",
    "        for k, v in permutation.items():\n",
    "            default = Counter([x1 for x1, y1 in v])[k[0]]\n",
    "            result = max(max(list(Counter([round((y1 - k[1]) / (x1 - k[0]), 10) for x1, y1 in v if x1 != k[0]]).values()) + [0]), default, result)\n",
    "        return result + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        length_points = len(points)\n",
    "\n",
    "        if length_points <= 2:\n",
    "            return length_points\n",
    "\n",
    "        used = [False] * length_points\n",
    "        group_line = []\n",
    "        max_line = 0\n",
    "\n",
    "        for i in range(length_points-2):\n",
    "            if used[i]:\n",
    "                continue\n",
    "\n",
    "            used[i] = True\n",
    "            \n",
    "            for j in range(i+1, length_points-1):\n",
    "                tan = self.__cal_tan__(points[i], points[j])\n",
    "                line = [points[i], points[j]]\n",
    "                for k in range(j+1, length_points):\n",
    "                    if self.__cal_tan__(points[i], points[k]) == tan:\n",
    "                        line.append(points[k])\n",
    "                        used[k] = True\n",
    "\n",
    "                group_line.append(line)\n",
    "                line_len = len(line)\n",
    "                max_line = max(line_len, max_line)\n",
    "                if line_len > length_points >> 1 or max_line > length_points - i:\n",
    "                    return max_line\n",
    "\n",
    "        return max(map(len, group_line))\n",
    "\n",
    "    def __cal_tan__(self, p1: List[int], p2: List[int]) -> float:\n",
    "        if p1[1] - p2[1] == 0:\n",
    "            return 1e9\n",
    "        return (p1[0] - p2[0]) / (p1[1] - p2[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        slopes = [[1.0] * n for _ in range(n)]\n",
    "        ans = 1\n",
    "        for i in range(n):\n",
    "            x1, y1 = points[i]\n",
    "            for j in range(i+1, n):\n",
    "                x2, y2 = points[j]\n",
    "                if x2 == x1:\n",
    "                    k = float('inf')\n",
    "                else:\n",
    "                    k = (y2 - y1) / (x2 - x1)\n",
    "                slopes[i][j] = k\n",
    "                slopes[j][i] = k\n",
    "            cnt = Counter(slopes[i])\n",
    "            k1 = max(cnt, key=lambda x: cnt[x])\n",
    "            t = cnt[k1]\n",
    "            if k1 != 1.0:\n",
    "                t += 1\n",
    "            ans = max(ans, t)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "\n",
    "        # 求最大公约数\n",
    "        def max_factor(p,q):\n",
    "            result = p%q\n",
    "            while result >0:\n",
    "                p = q\n",
    "                q = result\n",
    "                result = p%q\n",
    "            return q\n",
    "        # 统计数组重复最多的次数\n",
    "        def max_repeat(arr):\n",
    "            dic = dict()\n",
    "            for i in arr:\n",
    "                dic[i] = 0\n",
    "            for i in arr:\n",
    "                dic[i] = dic[i] + 1\n",
    "            return max(dic.values())\n",
    "\n",
    "        # dp[i][j]储存i与j+1的连线的最简（即无公因子，且第一个分量>=0）正切\n",
    "        dp = [['' for i in range(n-1)] for j in range(n-1)]\n",
    "\n",
    "        for i in range(n-1):\n",
    "            for j in range(i,n-1):\n",
    "                if points[i][0] == points[j+1][0]: # 如果连线垂直于x轴\n",
    "                    dp[i][j] = dp[i][j] + '0/1'\n",
    "                else:\n",
    "                    x = points[i][0] - points[j+1][0]\n",
    "                    y = points[i][1] - points[j+1][1]\n",
    "                    q = max_factor(abs(y),abs(x))\n",
    "                    x = x // q\n",
    "                    y = y // q\n",
    "                    dp[i][j] = dp[i][j] + str(abs(x)) + '/'\n",
    "                    if x*y<=0:\n",
    "                        dp[i][j] = dp[i][j] + str(-abs(y))\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i][j] + str(abs(y))\n",
    "        result = 0\n",
    "        for i in range(n-1):\n",
    "            x = dp[i][i:]\n",
    "            if result >= n-i-1:\n",
    "                break\n",
    "            result = max(result, max_repeat(x))\n",
    "        return result+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        y = len(points)\n",
    "        \n",
    "        v1,v2,v3 =[],[],[]\n",
    "        if y>1:\n",
    "            for i in range(y):\n",
    "                for j in range(i+1,y):\n",
    "                    m,n,l=2,2,2\n",
    "                    for k in range(y):\n",
    "                    \n",
    "                        if k!=i and k!=j:\n",
    "                            if points[i][0]==points[j][0] and points[i][0]==points[k][0]:n+=1\n",
    "                            if (points[i][1]==points[j][1]) and points[i][1]==points[k][1]:l+=1   \n",
    "                            if points[i][0]!=points[j][0] and points[i][1]!=points[j][1] and ((points[k][0]-points[j][0])/(points[i][0]-points[j][0]))==((points[k][1]-points[j][1])/(points[i][1]-points[j][1])):\n",
    "                                m+=1\n",
    "                    v1.append(n)\n",
    "                    v2.append(l)\n",
    "                    v3.append(m)\n",
    "                    \n",
    "            return(max(v1+v2+v3))\n",
    "        else:\n",
    "            return 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        res = 1\n",
    "        g = [set() for _ in range(n)]\n",
    "        for i in range(n-1):\n",
    "            m = dict()\n",
    "            for j in range(i+1,n):\n",
    "                dx = points[j][0] - points[i][0]\n",
    "                dy = points[j][1] - points[i][1]\n",
    "                if dx == 0:\n",
    "                    slope = 1e8+1\n",
    "                else:\n",
    "                    slope = dy / dx\n",
    "                if slope in g[i]:\n",
    "                    continue\n",
    "                if slope in m:\n",
    "                    m[slope] += 1\n",
    "                else:\n",
    "                    m[slope] = 2\n",
    "                g[j].add(slope)\n",
    "            if m:\n",
    "                res = max(res, max(m.values()))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        if len(points)<=1:\n",
    "            return len(points)\n",
    "        t=[]\n",
    "        for i in range(len(points)):\n",
    "            for j in range(i+1,len(points)):\n",
    "                t.append([points[i],points[j]])\n",
    "        more=[]\n",
    "        m=2\n",
    "        for i in t:\n",
    "            if i in more:\n",
    "                continue\n",
    "            n=2\n",
    "            for p in points:\n",
    "                if p in i:\n",
    "                    continue\n",
    "                x1=i[0][0]\n",
    "                y1=i[0][1]\n",
    "                x2=i[1][0]\n",
    "                y2=i[1][1]\n",
    "                x3=p[0]\n",
    "                y3=p[1]\n",
    "                if (x2==x1 and x3!=x1) or (x2!=x1 and x3==x1) or (x2!=x1 and x3==x2):\n",
    "                    continue\n",
    "                if (x2==x1 and x3==x1) or (y2-y1)/(x2-x1)==(y3-y1)/(x3-x1):\n",
    "                    n+=1\n",
    "                    #remove more points\n",
    "                    if [[x1,y1],[x3,y3]] in t:\n",
    "                        more.append([[x1,y1],[x3,y3]])\n",
    "                    if [[x3,y3],[x1,y1]] in t:\n",
    "                        more.append([[x3,y3],[x1,y1]])\n",
    "                    if [[x2,y2],[x3,y3]] in t:\n",
    "                        more.append([[x2,y2],[x3,y3]])\n",
    "                    if [[x3,y3],[x2,y2]] in t:\n",
    "                        more.append([[x3,y3],[x2,y2]])\n",
    "            if n>m:\n",
    "                m=n\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        # 迭代\n",
    "        # 数组存储每一个直线包含的点\n",
    "        lines = []\n",
    "        visited = []\n",
    "        if len(points) == 1: return 1\n",
    "        for point in points:\n",
    "            for line in lines:\n",
    "                one, two = line[-2], line[-1]\n",
    "                k1 = (two[1] - one[1]) / (two[0] - one[0]) if two[0] != one[0] else 'Inf'\n",
    "                k2 = (point[1] - one[1]) / (point[0] - one[0]) if point[0] != one[0] else 'Inf'\n",
    "                if k1 == k2:\n",
    "                    line.append(point)\n",
    "            for pre_point in visited:\n",
    "                lines.append([pre_point, point])\n",
    "            visited.append(point)\n",
    "        return max([len(line) for line in lines])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        n=len(points)\n",
    "        if n==1:\n",
    "            return 1\n",
    "        lines=[[i,j] for i in range(n-1) for j in range(i+1,n)]\n",
    "        for line in lines:\n",
    "            for k in range(n):\n",
    "                if k!=line[0] and k!=line[1]:\n",
    "                    if points[k][0]==points[line[0]][0] and points[k][0]==points[line[1]][0]:\n",
    "                        line.append(k)\n",
    "                    if points[k][1]==points[line[0]][1] and points[k][1]==points[line[1]][1]:\n",
    "                        line.append(k)\n",
    "                    dx1=points[line[1]][0] - points[line[0]][0]\n",
    "                    dy1=points[line[1]][1] - points[line[0]][1]\n",
    "                    dx2=points[k][0] - points[line[0]][0]\n",
    "                    dy2=points[k][1] - points[line[0]][1]\n",
    "                    if  dx1!=0 and dy1!=0 and dx2!=0 and dy2!=0 and dy1/dx1==dy2/dx2:\n",
    "                        line.append(k)\n",
    "        return max([len(x) for x in lines])\n",
    "                \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math \n",
    "class Solution:\n",
    "    def maxPoints(self, p: List[List[int]]) -> int:\n",
    "        def f(a, b):\n",
    "            x1, y1 = a \n",
    "            x2, y2 = b \n",
    "            if y1==y2:\n",
    "                return (1, 0)\n",
    "            if x1==x2:\n",
    "                return (0, 1)\n",
    "            z = math.gcd(y2 - y1, x2 - x1)\n",
    "            ans = ((y2 - y1)//z, (x2 - x1)//z)\n",
    "            if ans[1]>=0:\n",
    "                return ans \n",
    "            else:\n",
    "                return (-ans[0], -ans[1])\n",
    "        n = len(p)\n",
    "        ans = 1 \n",
    "        s = {}\n",
    "        for i in range(n):\n",
    "            t = defaultdict(int)\n",
    "            for j in range(i+1, n):\n",
    "                k = f(p[i], p[j])\n",
    "                t[k] += 1 \n",
    "            s[i] = t \n",
    "        for i in range(n):\n",
    "            if s[i]:\n",
    "                ans = max(max(s[i].values())+1, ans)\n",
    "        return ans \n",
    "\n",
    "                \n",
    "                \n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        if len(points) < 3:\n",
    "            return len(points)\n",
    "        max_count = 2\n",
    "        self.results = []\n",
    "        for i in range(len(points)):\n",
    "            for j in range(len(self.results)):\n",
    "                x, y, k, _ = self.results[j]\n",
    "                if points[i][0] == self.results[j][0]:\n",
    "                    new_k = float('inf')\n",
    "                else:\n",
    "                    new_k = (points[i][1] - self.results[j][1])/(points[i][0] - self.results[j][0])\n",
    "                if k is None:\n",
    "                    self.results.append([x, y, new_k, 2])\n",
    "                elif k == new_k:\n",
    "                    self.results[j][3] += 1\n",
    "                    if max_count < self.results[j][3]:\n",
    "                        max_count = self.results[j][3]\n",
    "            self.results.append([points[i][0], points[i][1], None, 1])\n",
    "        return max_count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        g = dict()\n",
    "        for x, y in points:\n",
    "            g[(x, y)] = Counter() \n",
    "        n = len(points)\n",
    "        for i in range(n):\n",
    "            x1, y1 = points[i]\n",
    "            for j in range(i+1, n):\n",
    "                x2, y2 = points[j]\n",
    "                if x1 != x2:\n",
    "                    angle = (y2 - y1) / (x2 - x1)\n",
    "                    s = str(angle)\n",
    "                else:\n",
    "                    s = 'inf'\n",
    "                g[(x1, y1)][s] += 1\n",
    "                g[(x2, y2)][s] += 1\n",
    "        return max(max(c.values(), default=0) for c in g.values()) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        count = len(points)\n",
    "        slopes = []\n",
    "        for i in range(count):\n",
    "            slope = []\n",
    "            for j in range(i):\n",
    "                slope.append(self.cal_slope(points[i], points[j]))\n",
    "            slopes.append(slope)\n",
    "\n",
    "        max_count = 0\n",
    "        target_point = i\n",
    "        for i in range(count):\n",
    "            slppe_count = {}\n",
    "            for j in range(i):\n",
    "                [m, n] = slopes[i][j]\n",
    "                key = str(m) + \"-\" + str(n)\n",
    "                sc = slppe_count.get(key, 0)\n",
    "                sc += 1\n",
    "                slppe_count[key] = sc\n",
    "                if sc > max_count:\n",
    "                    max_count = sc\n",
    "                    target_point = i\n",
    "            '''\n",
    "            for j in range(i + 1, count):\n",
    "                [m, n] = slopes[j][i]\n",
    "                key = str(m) + \"-\" + str(n)\n",
    "                sc = slppe_count.get(key, 0)\n",
    "                sc += 1\n",
    "                slppe_count[key] = sc\n",
    "                if sc > max_count:\n",
    "                    max_count = sc\n",
    "                    target_point = i\n",
    "            '''\n",
    "        #print(\"target_point=\", target_point, \"slopes=\", slopes)\n",
    "        return max_count + 1\n",
    "\n",
    "    def cal_slope(self, a, b):\n",
    "        [x1, y1] = a\n",
    "        [x2, y2] = b\n",
    "        m = x1 - x2\n",
    "        n = y1 - y2\n",
    "\n",
    "        if m == 0:\n",
    "            return [0, 1]\n",
    "        elif n == 0:\n",
    "            return [1, 0]\n",
    "        else:\n",
    "            flag = 1 if (m > 0 and n > 0) or (m < 0 and n < 0) else -1\n",
    "            m = m if m > 0 else -m\n",
    "            n = n if n > 0 else -n\n",
    "            div = self.gcd(m, n)\n",
    "            return [flag * m / div, n / div]\n",
    "\n",
    "    def gcd(self, m, n):\n",
    "        if m < n:\n",
    "            back = m\n",
    "            m = n\n",
    "            n = back\n",
    "        while m % n != 0:\n",
    "            mod = m % n\n",
    "            m = n\n",
    "            n = mod\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    ## 求最大公约数, 默认输入的 x, y 大于 0\n",
    "    def gcd(self, x, y):\n",
    "        if x > y:\n",
    "            return self.gcd(y, x)\n",
    "        if x == 0:\n",
    "            return y\n",
    "        return self.gcd(y%x, x)\n",
    "\n",
    "    def getSlope(self, point1, point2):\n",
    "        x1, y1, x2, y2 = point1[0], point1[1], point2[0], point2[1]\n",
    "        if x1 == x2:\n",
    "            return x1, 0\n",
    "        elif y1 == y2:\n",
    "            return 0, y1\n",
    "        else:\n",
    "            delta_x, delta_y = x2-x1, y2-y1\n",
    "            abs_delta_x, abs_delta_y = abs(x2-x1), abs(y2-y1)\n",
    "            if delta_x == 0 or delta_y == 0:\n",
    "                if delta_x == 0:\n",
    "                    return x1, 0\n",
    "                else:\n",
    "                    return 0, y1\n",
    "            else:\n",
    "                 ## 对斜率求最大公约数, 方便后续在字典中统计\n",
    "                gcd = self.gcd(abs_delta_x, abs_delta_y)\n",
    "                slope_x, slope_y = abs_delta_x/gcd, abs_delta_y/gcd\n",
    "                if (delta_x>0 and delta_y>0) or (delta_x<0 and delta_y<0):\n",
    "                    return slope_x, slope_y\n",
    "                else: # 斜率为负时, 返回的第一个为正，第二个为负\n",
    "                    return slope_x, -slope_y\n",
    "\n",
    "\n",
    "\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        if len(points) <= 2:\n",
    "            return len(points)\n",
    "        a = dict()\n",
    "        res = 2\n",
    "        for i in range(len(points)-1):\n",
    "            for j in range(i+1, len(points)):\n",
    "                x, y = self.getSlope(points[i], points[j])\n",
    "                key = str(points[i][0])+\":\"+str(points[i][1])+\":\"+str(x)+\":\"+str(y)\n",
    "                if key in a:\n",
    "                    a[key] = a[key]+1\n",
    "                else:\n",
    "                    a[key] = 1\n",
    "                if res < a[key]+1:\n",
    "                    res = a[key]+1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def euclidean(up, down):\n",
    "    if up == 0:\n",
    "        return 0, 0\n",
    "    flag_minus = (up * down) < 0\n",
    "    up, down = abs(up), abs(down)\n",
    "    if up == down:\n",
    "        return -1 if flag_minus else 1, 1\n",
    "\n",
    "    a, b = up, down\n",
    "    if a > b: a, b = b, a\n",
    "    r = b - a\n",
    "    while (a % r != 0) or (b % r != 0):\n",
    "        b = b - a\n",
    "        if a > b: a, b = b, a\n",
    "        r = b - a\n",
    "    up, down = up // r, down // r\n",
    "    if flag_minus:\n",
    "        up = -up\n",
    "    return up, down\n",
    "\n",
    "def cal_line(x1, y1, x2, y2):\n",
    "    if x1 == x2:\n",
    "        return f'x={x1}'\n",
    "    elif y1 == y2:\n",
    "        return f'y={y1}'\n",
    "    else:\n",
    "        # k = (y2-y1)/(x2-x1), b = (x2y1-x1y2)/(x2-x1)\n",
    "        return f'k={euclidean(y2-y1, x2-x1)}, b={euclidean(x2*y1-x1*y2, x2-x1)}'\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        if len(points) <= 2:\n",
    "            return len(points)\n",
    "\n",
    "        lines = {cal_line(points[0][0], points[0][1], points[1][0], points[1][1]): 2}\n",
    "        max_count = 2\n",
    "        for i in range(2, len(points)):\n",
    "            lines_i = {}\n",
    "            for x2, y2 in points[:i]:\n",
    "                lines_i[cal_line(points[i][0], points[i][1], x2, y2)] = ''\n",
    "            tmp = 0\n",
    "            for line in lines_i:\n",
    "                if line in lines:\n",
    "                    lines[line] += 1\n",
    "                    if max_count <  lines[line]:\n",
    "                        max_count = lines[line]\n",
    "                else:\n",
    "                    lines[line] = 2\n",
    "        return max_count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution(object):\n",
    "    def maxPoints(self, points):\n",
    "        \"\"\"\n",
    "        :type points: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(points) <= 2:\n",
    "            return len(points)\n",
    "\n",
    "        count_map = {}\n",
    "\n",
    "        for i in range(len(points)):\n",
    "            base_point = points[i]\n",
    "            # base_str = \"{}_{}\".format(base_point[0],base_point[1])\n",
    "\n",
    "            # print(\"base_point\", i, base_point)\n",
    "            for j in range(i+1, len(points)):\n",
    "                tmp_point = points[j]\n",
    "                # tmp_str = f\"{tmp_point[0]}_{tmp_point[1]}\"\n",
    "                # tmp_str = \"{}_{}\".format(tmp_point[0],tmp_point[1])\n",
    "                # print(\"tmp_point\", tmp_point)\n",
    "                k = \"k\"\n",
    "                if tmp_point[0] != base_point[0]:\n",
    "                    k = (tmp_point[1]-base_point[1])/(tmp_point[0]-base_point[0])\n",
    "                # print(\"tmp_point\", j, tmp_point, k)\n",
    "                exist = False\n",
    "                if k not in count_map:\n",
    "                    count_map[k] = []\n",
    "                for one in count_map[k]:\n",
    "                    if i in one:\n",
    "                        exist = True\n",
    "                        if j not in one:\n",
    "                            one.append(j)\n",
    "                        break\n",
    "                if exist is False:\n",
    "                    count_map[k].append([i,j])\n",
    "\n",
    "        max = 0\n",
    "        # print(count_map)\n",
    "        for one_k in count_map.values():\n",
    "            for one in one_k:\n",
    "                max = len(one) if len(one) > max else max\n",
    "        # print(max)\n",
    "        return max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        if len(points)==1:\n",
    "            return 1\n",
    "\n",
    "        lines = {}\n",
    "        n = len(points)\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1, n):\n",
    "                pa, pb = points[i], points[j]\n",
    "                if pa != pb:\n",
    "                    lines[(pa[0],pa[1], (pb[0]-pa[0]),(pb[1]-pa[1]))] = 1\n",
    "\n",
    "\n",
    "\n",
    "        for p in points:\n",
    "            for k in lines:\n",
    "                if not (p[0]==k[0] and p[1]==k[1]):\n",
    "                    if (p[1]-k[1]) * k[2] == (p[0]-k[0]) * k[3]:\n",
    "                        lines[k] += 1\n",
    "\n",
    "        return max(lines.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def is_same(self,slope1,slope2): # 判断斜率是否相同\n",
    "        if slope1[1] == 0 and slope2[1] == 0 and slope2[0]!=0: #如果两个斜率均为正无穷（竖着的直线）并且第二个点不是第i个点\n",
    "            return True\n",
    "        elif slope1[1] == 0 or slope2[1] == 0:                 #如果有一个斜率为正无穷，那么直接返回False\n",
    "            return False\n",
    "        else:\n",
    "            if slope1[0]/slope1[1] == slope2[0]/slope2[1]:     #斜率相同返回True\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        length = len(points)      #length为点的个数\n",
    "        if length == 1:           #如果只有一个点，直接返回1\n",
    "            return 1\n",
    "        slope = [[[0,0]for i in range(length)]for i in range(length)]  # 存储斜率 [x,y] 斜率 x/y\n",
    "        for i in range(length):\n",
    "            for j in range(i+1,length):  \n",
    "                slope[i][j][0] = points[j][0] - points[i][0]\n",
    "                slope[i][j][1] = points[j][1] - points[i][1]\n",
    "                # 获取斜率  [x,y] x = x1 - x0,  y = y1 - y0  ，slope[i][j]表示从点i到点j的斜率\n",
    "\n",
    "        set = 1\n",
    "        for i in range(length):  # i到j的斜率和j到i的斜率相同，把表填写完整\n",
    "            for j in range(set):\n",
    "                slope[i][j] = slope[j][i]\n",
    "            set += 1\n",
    "\n",
    "\n",
    "        #接下来就是查找每行出现最多相同斜率的个数即可，就是本题答案\n",
    "        count = 0\n",
    "        for i in range(length):\n",
    "            for j in range(length):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                else:\n",
    "                    flag = 1\n",
    "                    for k in range(length):\n",
    "                        if self.is_same(slope[i][j],slope[i][k]):\n",
    "                            flag += 1\n",
    "                    if flag > count:\n",
    "                        count = flag\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        # ax+by=c (a,b,c为元组)\n",
    "        \n",
    "        abc=dict()\n",
    "        used=[points[0]]\n",
    "        \n",
    "        for x1,y1 in points[1:]:\n",
    "            once=set()  #同样的直线只统计一次\n",
    "\n",
    "            for x0,y0 in used:\n",
    "                if x1==x0:\n",
    "                    if (1,0,x0) not in once:\n",
    "                        once.add((1,0,x0))\n",
    "                        if (1,0,x0) in abc:\n",
    "                            abc[(1,0,x0)]+=1\n",
    "                        else:    \n",
    "                            abc[(1,0,x0)] =2\n",
    "                elif y1==y0:\n",
    "                    if (0,1,y0) not in once:\n",
    "                        once.add((0,1,y0))\n",
    "                        if (0,1,y0) in abc:\n",
    "                            abc[(0,1,y0)]+=1\n",
    "                        else:    \n",
    "                            abc[(0,1,y0)] =2\n",
    "                else:\n",
    "                    a,c=(y1-y0)/(x0-x1),(x0*y1-x1*y0)/(x0-x1)\n",
    "                    if (a,1,c) not in once:\n",
    "                        once.add((a,1,c))\n",
    "                        if  (a,1,c) in abc:\n",
    "                            abc[(a,1,c)]+=1\n",
    "                        else:\n",
    "                            abc[(a,1,c)] =2  \n",
    "            used.append([x1,y1])    \n",
    "    \n",
    "        return max(abc.values()) if abc else 1  \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        abc=dict()              # ax+by=c (a,b,c为元组) 为了归一化，一般选择b为1. 平行x,y的直线 选择 a,b为1,0 或0,1\n",
    "        used=[points[0]]        # 采用过得点\n",
    "        for x1,y1 in points[1:]:\n",
    "            once=set()          #某一个点 x1,y1 只能在同一条直线上（a,b,c）统计一次。\n",
    "            for x0,y0 in used:\n",
    "                if x1==x0:\n",
    "                    if (1,0,x0) not in once:\n",
    "                        once.add((1,0,x0))\n",
    "                        if (1,0,x0) in abc:   #已有直线，增加一个点\n",
    "                            abc[(1,0,x0)]+=1\n",
    "                        else:    \n",
    "                            abc[(1,0,x0)] =2  #首次两点成线\n",
    "                elif y1==y0:\n",
    "                    if (0,1,y0) not in once:\n",
    "                        once.add((0,1,y0))\n",
    "                        if (0,1,y0) in abc:\n",
    "                            abc[(0,1,y0)]+=1\n",
    "                        else:    \n",
    "                            abc[(0,1,y0)] =2\n",
    "                else:\n",
    "                    a,c=(y1-y0)/(x0-x1),(x0*y1-x1*y0)/(x0-x1)\n",
    "                    if (a,1,c) not in once:\n",
    "                        once.add((a,1,c))\n",
    "                        if  (a,1,c) in abc:\n",
    "                            abc[(a,1,c)]+=1\n",
    "                        else:\n",
    "                            abc[(a,1,c)] =2  \n",
    "            used.append([x1,y1])    \n",
    "    \n",
    "        return max(abc.values()) if abc else 1  \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        # y1 = x1a + b\n",
    "        # y2 = x2a + b\n",
    "        if len(points) == 1:\n",
    "            return 1\n",
    "        def func(x1, y1, x2, y2):\n",
    "            if x2 - x1 != 0:\n",
    "                a = (y2 - y1) / (x2 - x1)\n",
    "            else:\n",
    "                return None, 'inf'\n",
    "            b = y1 - x1*a\n",
    "            return round(a, 12), round(b, 12)\n",
    "        dp = [[[0, 0] for _ in range(len(points))] for _ in range(len(points))]\n",
    "\n",
    "        max_ans = 2\n",
    "\n",
    "        for i in range(len(points)):\n",
    "            for j in range(i+1, len(points)):\n",
    "                ans = 2\n",
    "                p1 = points[i]\n",
    "                p2 = points[j]\n",
    "                dp[i][j] = func(p1[0], p1[1], p2[0], p2[1])\n",
    "                # print('---')\n",
    "                for k in range(j+1, len(points)):\n",
    "                    p3 = points[k]\n",
    "                    if dp[i][j] == func(p2[0], p2[1], p3[0], p3[1]):\n",
    "                        ans += 1\n",
    "                        # print(p1)\n",
    "                        # print(p3, func(p2[0], p2[1], p3[0], p3[1]))\n",
    "                        # print('ans', ans)\n",
    "                        max_ans = max(max_ans, ans)\n",
    "        \n",
    "        # print(max_ans)\n",
    "        return max_ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        from math import gcd\n",
    "        if len(points)==1:\n",
    "            return 1\n",
    "        m1=999\n",
    "        m2=999\n",
    "        map1={}\n",
    "        for i in range(len(points)):\n",
    "            for j in range(i+1,len(points)):\n",
    "                dx=points[i][0]-points[j][0]\n",
    "                dy=points[i][1]-points[j][1]\n",
    "                if dx==0:\n",
    "                    if points[i][0] in map1:\n",
    "                        map1[points[i][0]]+=1\n",
    "                    else:\n",
    "                        map1[points[i][0]]=1\n",
    "                else:\n",
    "                    xy=gcd(abs(dx),abs(dy))\n",
    "                    dx/=xy\n",
    "                    dy/=xy\n",
    "                    if dx<0:\n",
    "                        dx=-dx\n",
    "                        dy=-dy\n",
    "                    zz=dx*points[i][1]-dy*points[i][0]\n",
    "                    if (dy,dx,zz) in map1:\n",
    "                        map1[(dy,dx,zz)]+=1\n",
    "                    else:\n",
    "                        map1[(dy,dx,zz)]=1\n",
    "        return (int((max(map1.values())*2+0.25)**0.5+0.5))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        points.sort(key = lambda x:x[0])\n",
    "        n = len(points)\n",
    "        from collections import defaultdict\n",
    "        ans = defaultdict(int)\n",
    "        if n <=2:\n",
    "            return n\n",
    "\n",
    "        for i in range(n-1):\n",
    "            # print(\"i\",i,points[i])\n",
    "            for j in range(i+1,n):\n",
    "                # print(\"j\",j,points[j])\n",
    "                if points[j][0] == points[i][0]:\n",
    "                    kij = float(\"inf\")\n",
    "                    bij = points[i][0]\n",
    "                else:\n",
    "                    kij = (points[j][1] - points[i][1]) / ((points[j][0] - points[i][0]))\n",
    "                    bij = points[i][1] - kij*points[i][0]\n",
    "                # print(\"kij\",kij,bij)\n",
    "                # print(\"ans\",ans)\n",
    "                if (kij,bij) not in ans:\n",
    "                    ans[(kij,bij)] +=2\n",
    "                else:\n",
    "                    continue\n",
    "                for z in range(j+1,n):\n",
    "                    # print(\"z\",points[z])\n",
    "                    if points[z][0] == points[i][0]:\n",
    "                        kiz = float(\"inf\")\n",
    "                        biz = points[i][0]\n",
    "                    else:\n",
    "                        kiz = (points[z][1] - points[i][1]) / ((points[z][0] - points[i][0]))\n",
    "                        biz = points[i][1] - kiz*points[i][0]\n",
    "                    if kij == kiz and bij == biz:\n",
    "                        ans[(kij,bij)] +=1\n",
    "        ans = sorted(ans.items(),key=lambda x:x[1],reverse = True)\n",
    "        # print(\"ans\",ans)\n",
    "        return ans[0][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        line = defaultdict(list)\n",
    "        n = len(points)\n",
    "        if n <= 1:\n",
    "            return n\n",
    "        for i in range(n):\n",
    "            x = points[i]\n",
    "            for j in range(i+1, n):\n",
    "                y = points[j]\n",
    "                print(x, y)\n",
    "                if x[0] == y[0]:\n",
    "                    k = str(x[0])\n",
    "                else:\n",
    "                    beta = (y[1] - x[1])/(y[0] - x[0])\n",
    "                    alpha = y[1] - beta * y[0]\n",
    "                    k = \"{},{}\".format(beta, alpha)\n",
    "                if x not in line[k]:\n",
    "                    line[k].append(x)\n",
    "                if y not in line[k]:\n",
    "                    line[k].append(y)\n",
    "        return max([len(line[key]) for key in line.keys()])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        if len(points) < 3:\n",
    "            return len(points)\n",
    "        temp_set = set()\n",
    "        max_count = 2\n",
    "        self.results = []\n",
    "        for i in range(len(points)):\n",
    "            for j in range(len(self.results)):\n",
    "                x, y, k, _ = self.results[j]\n",
    "                if points[i][0] == self.results[j][0]:\n",
    "                    new_k = float('inf')\n",
    "                else:\n",
    "                    new_k = (points[i][1] - self.results[j][1])/(points[i][0] - self.results[j][0])\n",
    "                if k is None:\n",
    "                    temp = [x, y, new_k, 2]\n",
    "                    temp_str = str(temp)\n",
    "                    if temp_str not in temp_set:\n",
    "                        self.results.append(temp)\n",
    "                        temp_set.add(temp_str)\n",
    "                elif k == new_k:\n",
    "                    self.results[j][3] += 1\n",
    "                    if max_count < self.results[j][3]:\n",
    "                        max_count = self.results[j][3]\n",
    "            self.results.append([points[i][0], points[i][1], None, 1])\n",
    "        return max_count\n",
    "\n",
    "# class Solution:\n",
    "#     def maxPoints(self, points: List[List[int]]) -> int:\n",
    "#         if len(points) < 3:\n",
    "#             return len(points)\n",
    "#         max_count = 2\n",
    "#         self.results = []\n",
    "#         for i in range(len(points)):\n",
    "#             for j in range(len(self.results)):\n",
    "#                 x, y, k, _ = self.results[j]\n",
    "#                 if points[i][0] == self.results[j][0]:\n",
    "#                     new_k = float('inf')\n",
    "#                 else:\n",
    "#                     new_k = (points[i][1] - self.results[j][1])/(points[i][0] - self.results[j][0])\n",
    "#                 if k is None:\n",
    "#                     self.results.append([x, y, new_k, 2])\n",
    "#                 elif k == new_k:\n",
    "#                     self.results[j][3] += 1\n",
    "#                     if max_count < self.results[j][3]:\n",
    "#                         max_count = self.results[j][3]\n",
    "#             self.results.append([points[i][0], points[i][1], None, 1])\n",
    "#         return max_count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from fractions import Fraction\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        points = sorted(points)\n",
    "        points_num  = len(points)\n",
    "        first_x = points[0][0]\n",
    "        first_x_num = 0\n",
    "        line_dict = {}\n",
    "        while first_x_num < points_num:\n",
    "            if points[first_x_num][0] == first_x:\n",
    "                first_x_num += 1\n",
    "            else:\n",
    "                break\n",
    "        \n",
    "        vertical_max = first_x_num\n",
    "        if first_x_num < points_num:\n",
    "            now_x = points[first_x_num]\n",
    "        now_x_num = 0\n",
    "\n",
    "\n",
    "        for index in range(first_x_num,points_num):\n",
    "            x = points[index][0]\n",
    "            y = points[index][1]\n",
    "            if x == now_x:\n",
    "                now_x_num += 1\n",
    "            else:\n",
    "                vertical_max = max(vertical_max,now_x_num)\n",
    "                now_x = x\n",
    "                now_x_num = 1\n",
    "            for pre_x,pre_y in points[0:index+1-now_x_num]:\n",
    "                k = Fraction((pre_y-y),(pre_x-x))\n",
    "                b = y-k*x\n",
    "                # print(pre_x,pre_y)\n",
    "                # print(k,b)\n",
    "                if (k,b) in line_dict.keys():\n",
    "                    line_dict[(k,b)] += 1\n",
    "                else:\n",
    "                    line_dict[(k,b)] = 2\n",
    "            # print(line_dict)\n",
    "        vertical_max = max(vertical_max,now_x_num)\n",
    "        max_num = max(line_dict.values()) if line_dict else 0\n",
    "\n",
    "        temp_result = 2 if max_num else 0\n",
    "        temp = 2 if max_num else 0\n",
    "        print(max_num)\n",
    "        while max_num > 0:\n",
    "            if temp_result + temp < max_num:\n",
    "                temp_result += temp\n",
    "                temp += 1\n",
    "            elif temp_result + temp == max_num:\n",
    "                temp +=1\n",
    "                break\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        return max(temp,vertical_max)        \n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        # y-y1/y2-y1=x-x1/x2-x1\n",
    "        # y-y1=(x-x1)(y2-y1)/(x2-x1)\n",
    "        # k=y2-y1/x2-x1\n",
    "        # b=y1-x1*k\n",
    "        n=len(points)\n",
    "        if n==1:return 1\n",
    "        max_=1\n",
    "        d=defaultdict(list)\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                x1,y1=points[i]\n",
    "                x2,y2=points[j]\n",
    "                if x1==x2:\n",
    "                    k='inf'\n",
    "                    b=x1\n",
    "                else:\n",
    "                    k=(y2-y1)/(x2-x1)\n",
    "                    b=y1-x1*k\n",
    "                if points[i] not in d[(k,b)]:d[(k,b)].append(points[i])\n",
    "                if points[j] not in d[(k,b)]:d[(k,b)].append(points[j])\n",
    "                if len(d[(k,b)])>max_:max_=len(d[(k,b)])\n",
    "        return max_\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        if len(points) == 1:\n",
    "            return 1\n",
    "\n",
    "        line = defaultdict(list)\n",
    "        for i in range(len(points)):\n",
    "            for j in range(i + 1, len(points)):\n",
    "                x1, y1 = points[i]\n",
    "                x2, y2 = points[j]\n",
    "                if x1 == x2:\n",
    "                    k = float('inf')\n",
    "                    d = x1\n",
    "                elif y1 == y2:\n",
    "                    k = 0\n",
    "                    d = y1\n",
    "                else:\n",
    "                    k = (y1-y2) / (x1-x2)\n",
    "                    d = y1 - k * x1\n",
    "                if i not in line[(k,d)]:\n",
    "                    line[(k,d)].append(i)\n",
    "                if j not in line[(k,d)]:\n",
    "                    line[(k,d)].append(j)\n",
    "        return max([len(v) for v in line.values()])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        rs = min(n, 2)\n",
    "        allx = {}\n",
    "        ally = {}\n",
    "        for i in points:\n",
    "            if i[0] not in allx:\n",
    "                allx[i[0]] = 0\n",
    "            if i[1] not in ally:\n",
    "                ally[i[1]] = 0\n",
    "            allx[i[0]]+=1\n",
    "            ally[i[1]]+=1\n",
    "        kx=sorted(allx, key=lambda x: allx[x], reverse=True)\n",
    "        ky=sorted(ally, key=lambda x: ally[x], reverse=True)\n",
    "        \n",
    "        rs = max(allx[kx[0]],ally[ky[0]],rs)\n",
    "        def get_a(p1,p2):\n",
    "            x=p1[0]-p2[0]\n",
    "            y=p1[0]-p2[0]\n",
    "\n",
    "        visited = {}\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if points[j][0]==points[i][0]:\n",
    "                    continue\n",
    "                a = (points[i][1]-points[j][1])/(points[i][0]-points[j][0])\n",
    "                b = points[j][1] - a*points[j][0]\n",
    "                key = '{}_{}'.format(a, b)\n",
    "                if key in visited:\n",
    "                    continue\n",
    "\n",
    "                \n",
    "                cnt = 0\n",
    "                for k in range(n):\n",
    "                    x,y=points[k][0],points[k][1]\n",
    "                    if abs(y-a*x-b)<0.00001:\n",
    "                        cnt+=1\n",
    "                visited[key] = cnt\n",
    "                rs = max(rs, cnt)\n",
    "        print(visited)\n",
    "        return rs\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def maxPoints(self, points):\n",
    "        \"\"\"\n",
    "        :type points: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(points) <= 2:\n",
    "            return len(points)\n",
    "\n",
    "        count_map = {}\n",
    "\n",
    "        for i in range(len(points)):\n",
    "            base_point = points[i]\n",
    "            # base_str = \"{}_{}\".format(base_point[0],base_point[1])\n",
    "\n",
    "            # print(\"base_point\", i, base_point)\n",
    "            for j in range(i+1, len(points)):\n",
    "                tmp_point = points[j]\n",
    "                # tmp_str = f\"{tmp_point[0]}_{tmp_point[1]}\"\n",
    "                # tmp_str = \"{}_{}\".format(tmp_point[0],tmp_point[1])\n",
    "                # print(\"tmp_point\", tmp_point)\n",
    "                k = \"k\"\n",
    "                if tmp_point[0] != base_point[0]:\n",
    "                    k = (tmp_point[1]-base_point[1])/(tmp_point[0]-base_point[0])\n",
    "                # print(\"tmp_point\", j, tmp_point, k)\n",
    "                exist = False\n",
    "                if k not in count_map:\n",
    "                    count_map[k] = []\n",
    "                for one in count_map[k]:\n",
    "                    if i in one:\n",
    "                        exist = True\n",
    "                        one.add(j)\n",
    "                if exist is False:\n",
    "                    count_map[k].append(set([i,j]))\n",
    "\n",
    "        max = 0\n",
    "        # print(count_map)\n",
    "        for one_k in count_map.values():\n",
    "            for one in one_k:\n",
    "                # print(set(one))\n",
    "                max = len(one) if len(one) > max else max\n",
    "        # print(max)\n",
    "        return max\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        def gcd(a, b):\n",
    "            x, y = a, b\n",
    "            while b:\n",
    "                a, b = b, a % b\n",
    "            return (x//a, y//a)\n",
    "            \n",
    "        def get_result(points):\n",
    "            points.sort(key=lambda x: x[1])\n",
    "            points.sort(key=lambda x: x[0])\n",
    "\n",
    "            n = len(points)\n",
    "            dp = [{} for i in range(n)] # k: set([points_index])\n",
    "            max_len = 1\n",
    "            for i in range(1, n):\n",
    "                visited = set()\n",
    "                for j in range(i-1, -1, -1):\n",
    "                    if j not in visited:\n",
    "                        dx, dy = points[i][0] - points[j][0], points[i][1] - points[j][1]\n",
    "                        k = gcd(dx, dy)\n",
    "                        if k in dp[j]:\n",
    "                            dp[i][k] = dp[j][k].union(set([i]))\n",
    "                            visited = visited.union(dp[j][k])\n",
    "                        else:\n",
    "                            dp[i][k] = set([i, j])\n",
    "                        if len(dp[i][k]) > max_len:\n",
    "                            max_len = len(dp[i][k])\n",
    "            return max_len\n",
    "        return get_result(points)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        if len(points) == 1:\n",
    "            return 1\n",
    "        elif len(points) == 2:\n",
    "            return 2\n",
    "        slopes = []\n",
    "        for x1 in points:\n",
    "            for x2 in points:\n",
    "                if x1 != x2:\n",
    "                    if x1[0] != x2[0]:\n",
    "                        denominator = x1[0] - x2[0]\n",
    "                        numerator =  x1[1] - x2[1] \n",
    "                        c = round(numerator/denominator * -x1[0]+x1[1] , 4)\n",
    "                        slopes.append( (numerator/denominator,c) )\n",
    "                    else:\n",
    "                        slopes.append( (math.inf, x1[0]) )\n",
    "        c = Counter(slopes)\n",
    "        x = c.most_common(1)\n",
    "        # print(slopes, c, x)\n",
    "        return math.ceil(math.sqrt(x[0][1]))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        n=len(points)\n",
    "        if n==1:return n\n",
    "        cnt=defaultdict(dict)\n",
    "        \n",
    "        for i  in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                x0,y0=points[i]\n",
    "                x1,y1=points[j]\n",
    "                if x0==x1:\n",
    "                    # cnt[('w',x0)]+=1\n",
    "                    if not cnt['w']:\n",
    "                        cnt['w'][x0]=[i,j]\n",
    "                    else:\n",
    "                        for k,v in cnt['w'].items():\n",
    "                            if k==x0 and j not in v:\n",
    "                                cnt['w'][x0].append(j)\n",
    "\n",
    "                else:\n",
    "                    k=(y1-y0)/(x1-x0)\n",
    "                    k=0 if k==0 else k\n",
    "                    if not cnt[k] or ( i not in cnt[k] and  not any([i in v for u,v in cnt[k].items()])):\n",
    "                        cnt[k][i]=[i,j]\n",
    "                    elif i in cnt[k]:\n",
    "                        cnt[k][i].append(j)\n",
    "        print(cnt)\n",
    "        ans=0\n",
    "        for k,v in cnt.items():\n",
    "            for i,li in v.items():\n",
    "                if (m:=len(li))>ans:\n",
    "                    ans=m \n",
    "        return ans\n",
    "                    # cnt[(k,y0-(y1-y0)/(x1-x0)*x0)]+=1\n",
    "        # ans=0\n",
    "        # for k,v in cnt.items():\n",
    "        #     if v>ans:\n",
    "        #         ans=v\n",
    "        # print(ans,cnt)\n",
    "        # return 1+(int(-1+math.sqrt(1+ans<<3))>>1)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        if len(points)==1:\n",
    "            return 1\n",
    "        def get_kb(p1, p2):\n",
    "            x1, y1 = p1\n",
    "            x2, y2 = p2\n",
    "            if x2 == x1:\n",
    "                k = float(\"inf\")\n",
    "                b = x1\n",
    "            else:\n",
    "                k = (y2 - y1) / (x2 - x1)\n",
    "                b = y1 - k * x1\n",
    "            return round(k,6), round(b,6)\n",
    "        dirs = Counter(get_kb(points[i], points[j]) for i in range(len(points)) for j in range(i+1, len(points)))\n",
    "        print(dirs)\n",
    "        most = dirs.most_common(1)[0][1]\n",
    "        # x * (x-1) = 2most\n",
    "        # x*2 - x - 2most = 0\n",
    "        # x = 1+-sqrt(1+8most)/(2)\n",
    "        return int((sqrt(8*most+1)+1)/2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        if n == 1: return 1\n",
    "\n",
    "        vertical = {}\n",
    "        d = {}\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1, n):\n",
    "                x1, y1 = points[i][0], points[i][1]\n",
    "                x2, y2 = points[j][0], points[j][1]\n",
    "                if x1 == x2:\n",
    "                    if x1 not in vertical:\n",
    "                        vertical[x1] = [[i, j]]\n",
    "                    else:\n",
    "                        vertical[x1].append([i, j])\n",
    "                else:\n",
    "                    k = (y1 - y2) / (x1 - x2)\n",
    "                    b = (y2 * x1 - y1 * x2) / (x1 - x2)\n",
    "                    if (k, b) not in d:\n",
    "                        d[(k, b)] = [[i, j]]\n",
    "                    else:\n",
    "                        d[(k, b)].append([i, j])\n",
    "        maxL = 0\n",
    "        maxPairs = []\n",
    "        for pairs in list(d.values()) + list(vertical.values()):\n",
    "            if len(pairs) > maxL:\n",
    "                maxL = len(pairs)\n",
    "                maxPairs = pairs\n",
    "        allPoints = set()\n",
    "        for pair in maxPairs:\n",
    "            allPoints.add(pair[0])\n",
    "            allPoints.add(pair[1])\n",
    "        return len(allPoints)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def compute_rate(x1,x2,y1,y2) -> float:\n",
    "            if x1 == x2:\n",
    "                return float(inf)\n",
    "            else:\n",
    "                return (y1 - y2) / (x1 - x2)\n",
    "\n",
    "        n = len(points)\n",
    "        stop = n / 2 + 1\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            count_dic = dict()\n",
    "            for j in range(n):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                rate = compute_rate(points[i][0], points[j][0],points[i][1], points[j][1])\n",
    "                if count_dic.get(rate):\n",
    "                    count_dic[rate] += 1\n",
    "                else:\n",
    "                    count_dic[rate] = 1\n",
    "            res = max(res, max(count_dic.values())+1)\n",
    "            if res > stop:\n",
    "                return res\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: list[list[int]]) -> int:\n",
    "        dic = {}\n",
    "        if len(points) == 1:\n",
    "            return 1\n",
    "        for i in range(len(points) - 1):\n",
    "            for j in range(i + 1, len(points)):\n",
    "                if j == len(points):\n",
    "                    break\n",
    "                if points[i][0] - points[j][0] == 0:\n",
    "                    if not dic.get('k1'+str(points[i][0])):\n",
    "                        dic['k1'+str(points[i][0])] = {i, j}\n",
    "                    else:\n",
    "                        dic['k1'+str(points[i][0])].add(j)\n",
    "                else:\n",
    "                    k = (points[i][1] - points[j][1]) / (points[i][0] - points[ j][0])\n",
    "                    b = points[i][1] - k * (points[i][0])\n",
    "                    if k == -0.0:\n",
    "                        k = 0.0\n",
    "\n",
    "                    if not dic.get(str(k) + str(b)):\n",
    "                        dic[str(k) + str(b)] = {i, j}\n",
    "                    else:\n",
    "                        dic[str(k) + str(b)].add(j)\n",
    "        ans = 0\n",
    "        for i in dic.values():\n",
    "            ans = max(ans, len(i))\n",
    "        # for i, j in dic.items():\n",
    "        #     print(i, j)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        if len(points) == 1:\n",
    "            return 1\n",
    "        segments = []\n",
    "\n",
    "        def gcd(a, b):\n",
    "            if b== 0:\n",
    "                return a\n",
    "            return gcd(b, a%b)\n",
    "        \n",
    "        pointMap = {}\n",
    "        # (a, b, c): (x, y)\n",
    "\n",
    "        for i in range(len(points)):\n",
    "            for j in range(i):\n",
    "                b = points[i][0] - points[j][0]\n",
    "                a = points[j][1] - points[i][1]\n",
    "                minus = False\n",
    "                if (a>=0 and b>=0) or a==0 or b==0:\n",
    "                    pass\n",
    "                elif a>0:\n",
    "                    minus = True\n",
    "                    b = -b\n",
    "                elif b>0:\n",
    "                    minus = True\n",
    "                    a = -a\n",
    "                else:\n",
    "                    a = -a\n",
    "                    b = -b\n",
    "\n",
    "                g = gcd(a, b)\n",
    "                a //= g\n",
    "                b //= g\n",
    "                if minus:\n",
    "                    b *= -1\n",
    "                \n",
    "                triple = (a, b, a*points[i][0]+b*points[i][1])\n",
    "                if triple not in pointMap:\n",
    "                    pointMap[triple] = set()\n",
    "                # pointMap[triple].add(i)\n",
    "                pointMap[triple].add(j)\n",
    "        return max([len(i)+1 for i in pointMap.values()])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        if len(points) == 1:\n",
    "            return 1\n",
    "        segments = []\n",
    "\n",
    "        def gcd(a, b):\n",
    "            if b== 0:\n",
    "                return a\n",
    "            return gcd(b, a%b)\n",
    "        \n",
    "        pointMap = {}\n",
    "        # (a, b, c): (x, y)\n",
    "\n",
    "        for i in range(len(points)):\n",
    "            for j in range(i):\n",
    "                b = points[i][0] - points[j][0]\n",
    "                a = points[j][1] - points[i][1]\n",
    "                minus = False\n",
    "                if (a>=0 and b>=0) or a==0 or b==0:\n",
    "                    pass\n",
    "                elif a>0:\n",
    "                    minus = True\n",
    "                    b = -b\n",
    "                elif b>0:\n",
    "                    minus = True\n",
    "                    a = -a\n",
    "                else:\n",
    "                    a = -a\n",
    "                    b = -b\n",
    "\n",
    "                g = gcd(a, b)\n",
    "                a //= g\n",
    "                b //= g\n",
    "                if minus:\n",
    "                    b *= -1\n",
    "                \n",
    "                triple = (a, b, a*points[i][0]+b*points[i][1])\n",
    "                if triple not in pointMap:\n",
    "                    pointMap[triple] = set()\n",
    "                pointMap[triple].add(i)\n",
    "                pointMap[triple].add(j)\n",
    "        return max([len(i) for i in pointMap.values()])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        N = len(points)\n",
    "        if N==1:\n",
    "            return 1\n",
    "        M = 0\n",
    "        lineDict = {}\n",
    "        for i in range(N - 1):\n",
    "            for j in range(i+1, N):\n",
    "                if points[i][0]==points[j][0]:\n",
    "                    tmp = (float(\"inf\"), points[i][0])\n",
    "                    if tmp not in lineDict:\n",
    "                        lineDict[tmp] = {i, j}\n",
    "                    else:\n",
    "                        lineDict[tmp].add(i)\n",
    "                        lineDict[tmp].add(j)\n",
    "                else:\n",
    "                    k = (points[i][1] - points[j][1]) / (points[i][0] - points[j][0])\n",
    "                    b = points[i][1] - k * points[i][0]\n",
    "                    if (k, b) not in lineDict:\n",
    "                        lineDict[(k, b)] = {i, j}\n",
    "                    else:\n",
    "                        lineDict[(k, b)].add(i)\n",
    "                        lineDict[(k, b)].add(j)\n",
    "        for key in lineDict:\n",
    "            if len(lineDict[key]) > M:\n",
    "                M = len(lineDict[key])\n",
    "        return M\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        d = defaultdict(set)\n",
    "        mx = 0\n",
    "        for i in range(n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                x1, x2, y1, y2 = points[i][0], points[j][0], points[i][1], points[j][1]\n",
    "                if x1 - x2 == 0:\n",
    "                    lr = float(\"inf\")\n",
    "                    bs = x1\n",
    "                else:\n",
    "                    lr = (y1 - y2) / (x1 - x2)\n",
    "                    bs = y1 - lr * x1\n",
    "                # print((lr, bs), (i, j))\n",
    "                d[(lr, bs)].add(i)\n",
    "                d[(lr, bs)].add(j)\n",
    "        for key in d:\n",
    "            mx = max(mx, len(d[key]))\n",
    "        # print(d)\n",
    "\n",
    "        return mx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        if n <= 1:\n",
    "            return n\n",
    "        k_map = defaultdict(list)\n",
    "        max_num = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                if points[i][0] - points[j][0] == 0:\n",
    "                    k = \"vert\"\n",
    "                else:\n",
    "                    k = (points[j][1] - points[i][1]) / (points[j][0] - points[i][0])\n",
    "                find_same_k = False\n",
    "                for set_k in k_map[k]:\n",
    "                    set_iter = iter(set_k)\n",
    "                    select_one = next(set_iter)\n",
    "                    if tuple(points[i]) in set_k or tuple(points[j]) in set_k or (\n",
    "                                k != \"vert\" and points[j][0] - select_one[0]!=0 and \n",
    "                                k == (points[j][1] - select_one[1]) / (points[j][0] - select_one[0])\n",
    "                            ) or (\n",
    "                                k == \"vert\" and points[i][0] == select_one[0]\n",
    "                        ):\n",
    "                        set_k.add(tuple(points[i]))\n",
    "                        set_k.add(tuple(points[j]))\n",
    "                        find_same_k = True\n",
    "                        max_num = max(max_num, len(set_k))\n",
    "                        break\n",
    "                if not find_same_k:\n",
    "                    k_map[k].append(set([tuple(points[i]), tuple(points[j])]))\n",
    "                    max_num = max(max_num, 2)\n",
    "                        \n",
    "        return max_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        # y = kx + b\n",
    "        dk = {}\n",
    "        for x1,y1 in points:\n",
    "            for x2,y2 in points:\n",
    "                if x2 == x1 and y2 == y1:\n",
    "                    continue\n",
    "                if x2-x1 == 0:\n",
    "                    k = 10000\n",
    "                    b = x1\n",
    "                else:\n",
    "                    k = ((y2-y1)*1000)/((x2-x1)*1000)\n",
    "                    b = round(y2 - k*x2, 2)\n",
    "                dk.setdefault(k,{})\n",
    "                dk[k].setdefault(b,[])\n",
    "                if [x2,y2] in dk[k][b]:\n",
    "                    continue\n",
    "                dk[k][b].append([x2,y2])\n",
    "        res = 1\n",
    "        for _, db in dk.items():\n",
    "            for _, lstP in db.items():\n",
    "                ilen = len(lstP)\n",
    "                if ilen > res:\n",
    "                    res = ilen\n",
    "        \n",
    "        return res\n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
